package q22_generateParenthesis;

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;

public class Solution_1 {
    public static void main(String[] args) {
        System.out.println(generateParenthesis(1));
    }

    public static List<String> generateParenthesis(int n) {
        // 递归，向generate(n-1)的每一个空插入一个'()'即可
        List<String> res = new ArrayList<>();
        if (n == 1) {
            res.add("()");
            return res;
        }

        for (String parenthesisBefore : generateParenthesis(n - 1)) {
            int len = parenthesisBefore.length();
            for (int i = 0; i < len; i++) {
                StringBuilder sb = new StringBuilder(parenthesisBefore);
                sb.insert(i,"()");
                res.add(sb.toString());
            }

        }
        LinkedHashSet<String> hashSet = new LinkedHashSet<>(res);
        return new ArrayList<>(hashSet);
    }
}
